1. Field
Embodiments of this invention relate generally to scheduling tasks on one or more processors.
2. Background
Internet websites and other large-scale online user applications receive numerous queries and information requests based on common user operations. For instance, a user may visit a website or access an application and begin selecting certain options for viewing purposes, information retrieval, etc. The users' expectations include instant feedback in real-time. As a result, users may become unsatisfied with any website or application that fails to provide such instant feedback.
As applications become increasingly complicated and require the use of multiple database informiation retrieval, remote access requests, and other information retrieval services, it may become increasingly difficult to satisfy user requests. Such requests may become even more challenging when faced with simultaneously servicing numerous such requests at any instant in time.
Services that translate queries include websites, such as mapping services, which may require actual geo-location calculations and database information retrieval all within a matter of seconds. Globally accessible websites may receive several thousand queries a second generating multiple corresponding jobs. These queries or requests must be organized and separated into jobs having corresponding tasks. For example, one large group of jobs may be modified into smaller groups, which may, in turn, have corresponding dependencies on each other.
Minimizing the response time for performing the query and returning it back to the user may pose challenges. The execution times of the jobs and tasks may be unknown and unpredictable. Various different tasks may require different amounts of time to process. If the execution times were well established it may be easier to organize the task processing times. Organizing task types may be one way to estimate an execution time. However, designating a single task as requiring a certain execution time without fault raises uncertainties.